// https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

// 算法思路总结：
// 1. 使用最小堆贪心处理K次取反操作
// 2. 每次对最小元素取反，优化整体和最大化
// 3. 利用最小堆快速获取当前最小元素
// 4. 时间复杂度：O(n+klogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>

class Solution 
{
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) 
    {
        int m = nums.size();

        priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());
        while (k > 0)
        {
            k--;
            int top = minHeap.top();
            minHeap.pop();
            top = -top;
            minHeap.push(top);
        }

        int ret = 0;
        while (!minHeap.empty())
        {
            int top = minHeap.top();
            ret += top;
            minHeap.pop();
        }

        return ret;
    }
};

int main()
{
    int k1 = 1, k2 = 3;
    vector<int> v1 = {4,2,3}, v2 = {3,-1,0,2};
    Solution sol;

    cout << sol.largestSumAfterKNegations(v1, k1) << endl;
    cout << sol.largestSumAfterKNegations(v2, k2) << endl;

    return 0;
}